package com.jiang.daily.Q790;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/05/05 21:30
 */
class Solution {
    final int MOD = 1_000_000_007;

    // 动态规划
    public int numTilings(int n) {
        int[][] dp = new int[n + 1][4]; // 铺到第 i 列时，各个状态 j 对应的平铺方法数量。 在铺第i列时，i列之前一定全部铺完，第i列可能会受到第i - 1列的影响；

        // 一个砖块都没有被覆盖，记为状态 0；

        // 只有上方的砖块被覆盖，记为状态 1；

        // 只有下方的砖块被覆盖，记为状态 2；

        // 上下两个砖块都被覆盖，记为状态 3。

        dp[0][3] = 1; // 在第0列之前没有-1列；前面的列不会影响到第0列，不可能出现任何状态；在第0列中铺满方法是不用多米诺，dp[0][3]数量为1。
        for (int i = 1; i <= n; i++) {
            dp[i][0] = dp[i - 1][3]; // 第i列都没有铺，说明第i - 1列没有影响到第i列，因为第i - 1列一定要铺满，所以看第i - 1列铺完的情况。

            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD; // 第i列的上面砖块被铺，那么第i - 1列影响到第i列的情况就是两种，一是第i - 1列都没有铺， 那么在i - 1列就需要用 "L" 多米诺铺 像这样"Г"铺 ，铺满 i - 1列并且第i列的上面就会被砖块铺； 二是第i - 1列的下面砖块铺了，那么在i-1列就需要用 2 × 1的多米诺 横着放在上面，从而铺满 i - 1列、第i列的上面就会被砖块铺

            dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD; // 第i列的下面砖块被铺，那么第i - 1列影响到第i列的情况就是两种，一是第i - 1列都没有被铺， 那么在i - 1列就需要用 "L" 多米诺铺 像这样"L"铺 ，铺满 i - 1列并且第i列的下面就会被砖块铺； 二是第i - 1列的上面砖块铺了，那么在i - 1列就需要用 2 × 1的多米诺 横着放在下面，从而铺满 i - 1列、第i列的下面就会被砖块铺

            dp[i][3] = (int) ((0L + dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD + dp[i - 1][3]) % MOD; // 第i列铺满，那么i - 1列影响到第i列就有4种情况，一是第i - 1列都没铺，那么在i - 1列就需要用 2 × 1的两个多米诺 横着铺； 二是第i - 1列的上面砖块铺了，那么在i - 1列就需要用 "L" 多米诺铺 像这样"𠃎"铺 ，铺满i - 1列和i列； 三是第i - 1列的下面砖块铺了，那么在i - 1列就需要用 "L" 多米诺铺 像这样"𠃍"铺 ，铺满 i - 1列和i列； 四是第i - 1列全部铺满， 这样第i - 1列没有影响到第i列，那么在第i - 1列铺多米诺时，就会用2 × 1的多米诺 竖着铺第i - 1列和第i列，这样就会影响。
        }

        return dp[n][3]; // 最后返回就是0~n列全部铺完的方法数量
    }
}
